package com.leetcodehot.problems;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

public class problems239 {
    /**
     * 假设用堆来实现
     * 那就需要构建一个k大根堆，并且需要实现右滑的时候加入且删除某个value
     * 删除的话会发现查找较为费劲
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            //入，维护队列的单调性，我们现在维护的是单调递减的队列
            while (!q.isEmpty() && nums[q.getLast()] <= x) {
                q.removeLast();
            }
            q.addLast(i);
            //出
            if (i - q.getFirst() >= k) {
                q.removeFirst();
            }

            //结果
            if (i > k - 2) {
                res[i - k + 1] = nums[q.getFirst()];
            }
        }
        return res;
    }
}

